package 动态规划.可dp可二分;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/10 10:22
 */
public class 数组分成k组再思考 {
    /*
    这里进行一个小小的
    对递归的 basecase 的一个优化
    在写暴力 递归 首先思考一下
    这个 basecase 怎么去写，怎么写是 最合理的
     */
    public int solution(int nums [],int k){
        int len = nums.length - 1;
        return recursion(0,k,len - 1);
    }

    /**
     *
     * @param index 就是当前元素的索引
     * @param k 剩余的 要分 的组的个数
     * @param r  len - 1， 这里设置 为 len - 1是 有道理的
     * @return
     */
    private int recursion(int index, int k, int r) {
//        if(index == r)
//            return k == 1 ? 1 : 0;
        // 这里写的 就很灵性，这里即使不写 下面这个basecase，的话最终还是 会进入 上面这个basecase 当中
        // 但是 写了这个 basecase 就可以提前 返回，没必要再进行 很多层递归才返回 1
        if(k == 1)
            return 1;
        int ans = 0;
        for(int scale = 1;index + scale <= r;scale ++){
            ans += recursion(index + scale,k - 1,r);
        }
        return ans;
    }


    public int dp(int number,int k){
        // number 是数组的一个长度
        int dp[][] = new int[number][k + 1];
        for(int index = number - 1;index >= 0;index --){
            // 初始化 dp[index][1] = 1;
            dp[index][1] = 1;
            for(int x = 2;x <= k;x++){
                int ans = 0;
                for(int scale = 1;scale + index <= number - 1;scale ++){
                    ans += dp[index + scale][x - 1];
                }
                dp[index][x] = ans;
            }
        }
        return dp[0][k];
    }

    public static void main(String[] args) {
//        int nums [] =
        int recursion = new 数组分成k组再思考().recursion(0, 3, 7);
        int recursion1 = new 数组分成k组再思考().dp(8,3);
        System.out.println(recursion);
        System.out.println(recursion1);
    }

}
